class Solution
{
public:
    long long countPairs(int n, vector<vector<int>> &edges)
    {
        vector<int> ufs(n);
        vector<int> size(n, 1);
        iota(ufs.begin(), ufs.end(), 0);

        function<int(int)> find = [&](int x)
        {
            return ufs[x] == x ? x : ufs[x] = find(ufs[x]);
        };

        function<void(int, int)> merge = [&](int x, int y)
        {
            x = find(x);
            y = find(y);
            if (x == y)
            {
                return;
            }
            if (size[x] < size[y])
            {
                swap(x, y);
            }
            ufs[y] = x;
            size[x] += size[y];
        };

        for (auto &edge : edges)
        {
            merge(edge[0], edge[1]);
        }

        unordered_map<long long, long long> sizeCount;
        unordered_set<int> visited;
        for (int i = 0; i < n; ++i)
        {
            int root = find(i);
            if (visited.count(root))
            {
                continue;
            }
            visited.insert(root);
            sizeCount[size[root]]++;
        }

        long long result = 0;
        for (auto i = sizeCount.begin(); i != sizeCount.end(); ++i)
        {
            result += i->second * (i->second - 1) / 2 * i->first * i->first;
            for (auto j = next(i); j != sizeCount.end(); ++j)
            {
                result += i->first * j->first * i->second * j->second;
            }
        }
        return result;
    }
};